<HTML><HEAD><TITLE>library(fd_sets)</TITLE></HEAD><BODY>
[ <A HREF="../../index.html">Reference Manual</A> | <A HREF="../../fullindex.html">Alphabetic Index</A> ]<H1>library(fd_sets)</H1>
Solver over sets of integers (cooperates with lib(fd))
<H2>Predicates</H2>
<BLOCKQUOTE>
<DL>
<DT><A HREF="H-2.html"><STRONG>#(?Set, ?Card)</STRONG></A></DT>
<DD>Card is the cardinality of the integer set Set</DD>
<DT><A HREF="NN-2.html"><STRONG>?Set :: ++Lwb..++Upb</STRONG></A></DT>
<DD>Set is an integer set within the given bounds</DD>
<DT><A HREF="all_disjoint-1.html"><STRONG>all_disjoint(+Sets)</STRONG></A></DT>
<DD>Sets is a list of integers sets which are all disjoint</DD>
<DT><A HREF="all_intersection-2.html"><STRONG>all_intersection(+Sets, ?Intersection)</STRONG></A></DT>
<DD>Intersection is the intersection of all the sets in the list Sets</DD>
<DT><A HREF="all_union-2.html"><STRONG>all_union(+Sets, ?SetUnion)</STRONG></A></DT>
<DD>SetUnion is the union of all the sets in the list Sets</DD>
<DT><A HREF="difference-3.html"><STRONG>difference(?Set1, ?Set2, ?Set3)</STRONG></A></DT>
<DD>Set3 is the difference of the integer sets Set1 and Set2</DD>
<DT><A HREF="disjoint-2.html"><STRONG>?Set1 disjoint ?Set2</STRONG></A></DT>
<DD>The integer sets Set1 and Set2 are disjoint</DD>
<DT><A HREF="get_set_attribute-2.html"><STRONG>get_set_attribute(?Set, -Attr)</STRONG></A></DT>
<DD>Get the set-attribute corresponding to Set</DD>
<DT><A HREF="in-2.html"><STRONG>?X in ?Set</STRONG></A></DT>
<DD>The integer X is member of the integer set Set</DD>
<DT><A HREF="in-3.html"><STRONG>in(?X, ?Set, ?Bool)</STRONG></A></DT>
<DD>Reified version of the set membership constraint</DD>
<DT><A HREF="in_set_range-2.html"><STRONG>?Set in_set_range ++Lwb..++Upb</STRONG></A></DT>
<DD>Set is an integer set within the given bounds</DD>
<DT><A HREF="includes-2.html"><STRONG>?Set1 includes ?Set2</STRONG></A></DT>
<DD>Set1 includes (is a superset of) the integer set Set2</DD>
<DT><A HREF="insetdomain-4.html"><STRONG>insetdomain(?Set, ?CardSel, ?ElemSel, ?Order)</STRONG></A></DT>
<DD>Instantiate Set to a possible value</DD>
<DT><A HREF="intersection-3.html"><STRONG>intersection(?Set1, ?Set2, ?Set3)</STRONG></A></DT>
<DD>Set3 is the intersection of the integer sets Set1 and Set2</DD>
<DT><A HREF="intset-3.html"><STRONG>intset(?Set, +Min, +Max)</STRONG></A></DT>
<DD>Set is a set containing numbers between Min and Max</DD>
<DT><A HREF="intsets-4.html"><STRONG>intsets(?Sets, ?N, +Min, +Max)</STRONG></A></DT>
<DD>Sets is a list of N sets containing numbers between Min and Max</DD>
<DT><A HREF="is_solver_type-1.html"><STRONG>is_solver_type(?Term)</STRONG></A></DT>
<DD>Succeeds if Term is a ground set or a set variable</DD>
<DT><A HREF="is_solver_var-1.html"><STRONG>is_solver_var(?Term)</STRONG></A></DT>
<DD>Succeeds if Term is a set variable</DD>
<DT><A HREF="membership_booleans-2.html"><STRONG>membership_booleans(?Set, ?BoolArr)</STRONG></A></DT>
<DD>BoolArr is an array of booleans describing Set</DD>
<DT><A HREF="notin-2.html"><STRONG>?X notin ?Set</STRONG></A></DT>
<DD>The integer X is not a member of the integer set Set</DD>
<DT><A HREF="potential_members-2.html"><STRONG>potential_members(?Set, -List)</STRONG></A></DT>
<DD>List is the list of elements of whose membership in Set is currently uncertain</DD>
<DT><A HREF="sameset-2.html"><STRONG>?Set1 sameset ?Set2</STRONG></A></DT>
<DD>The sets Set1 and Set2 are equal</DD>
<DT><A HREF="set_range-3.html"><STRONG>set_range(?Set, -Lwb, -Upb)</STRONG></A></DT>
<DD>Lwb and Upb are the current lower and upper bounds on Set</DD>
<DT><A HREF="subset-2.html"><STRONG>?Set1 subset ?Set2</STRONG></A></DT>
<DD>Set1 is a (non-strict) subset of the integer set Set2</DD>
<DT><A HREF="subsetof-2.html"><STRONG>?Set1 subsetof ?Set2</STRONG></A></DT>
<DD>Set1 is a (non-strict) subset of the integer set Set2</DD>
<DT><A HREF="symdiff-3.html"><STRONG>symdiff(?Set1, ?Set2, ?Set3)</STRONG></A></DT>
<DD>Set3 is the symmetric difference of the integer sets Set1 and Set2</DD>
<DT><A HREF="union-3.html"><STRONG>union(?Set1, ?Set2, ?Set3)</STRONG></A></DT>
<DD>Set3 is the union of the integer sets Set1 and Set2</DD>
<DT><STRONG>watch(?)</STRONG></DT>
<DD>No description available</DD>
<DT><A HREF="weight-3.html"><STRONG>weight(?Set, ++ElementWeights, ?Weight)</STRONG></A></DT>
<DD>According to the array of element weights, the weight of set Set is Weight</DD>
</DL>
</BLOCKQUOTE>
<H2>Structures</H2>
<BLOCKQUOTE>
<DL>
<DT><A HREF="int_sets-s.html"><STRONG>struct int_sets(dom, off, lcard, ucard, added, removed, add, rem, card, booleans, value)</STRONG></A></DT>
<DD>Attribute structure for set variables (and constants)</DD>
</DL>
</BLOCKQUOTE>
<H2>Other Exports</H2>
<BLOCKQUOTE><DL>
<DT><STRONG>export op(500, yfx, \)</STRONG></DT><DD></DD>
<DT><STRONG>export op(700, xfx, in_set_range)</STRONG></DT><DD></DD>
<DT><STRONG>export op(700, xfx, disjoint)</STRONG></DT><DD></DD>
<DT><STRONG>export op(700, xfx, sameset)</STRONG></DT><DD></DD>
<DT><STRONG>export op(700, xfx, in)</STRONG></DT><DD></DD>
<DT><STRONG>export op(700, xfx, notin)</STRONG></DT><DD></DD>
<DT><STRONG>export op(700, xfx, includes)</STRONG></DT><DD></DD>
<DT><STRONG>export op(700, xfx, subset)</STRONG></DT><DD></DD>
<DT><STRONG>export op(700, xfx, subsetof)</STRONG></DT><DD></DD>
</DL></BLOCKQUOTE>
<H2>Description</H2>

    This is a solver for constraints over the domain of finite integer sets.
    </P><P>
    (Ground) integer sets are represented simply as sorted, duplicate-free
    lists of integers e.g.
    <PRE>
    	SetOfThree = [1,3,7]
    	EmptySet = []
    </PRE>

<H3>Set Variables</H3>
    Set variables are variables which can eventually take a ground integer
    set as their value. They are characterized by a lower bound (the set 
    of elements that are definitely in the set) and an upper bound (the
    set of elements that may be in the set). A set variable can be declared
    as follows:
    <PRE>
    	SetVar :: []..[1,2,3,4,5,6,7],
    </PRE>
    Since the lower bound is the empty set, this can be written as
    <PRE>
    	SetVar subset [1,2,3,4,5,6,7],
    </PRE>
    If the lower bound is the empty set and the upper bound is a set
    of consecutive integers, you can also write
    <PRE>
    	intset(SetVar, 1, 7)
    </PRE>

<H3>Set Constraints</H3>
    Most of the usual set operations/relations are provided as constraints:
    <UL>
    <LI>membership
    <LI>non-membership
    <LI>inclusion (subset)
    <LI>equality
    <LI>intersection
    <LI>union
    <LI>difference
    <LI>symmetric difference
    <LI>disjointness
    <LI>cardinality
    </UL>
    as well as a constraint on set weight.  Note that there is no
    complement-constraint because the library has no concept of a set
    universe and cannot represent infinite sets.
    </P><P>
    On most argument positions where sets are expected, set expressions
    are allowed, e.g.
    <PRE>
    Set1 /\ Set2       % intersection
    Set1 \/ Set2       % union
    Set1 \ Set2        % difference
    </PRE>
    as well as references to array elements like Set[3].
    </P>

<H3>Search</H3>
    The insetdomain/4 predicate can be used to enumerate all ground
    instantiations of a set variable, much like indomain/1 in the
    finite-domain case.

<H3>Cooperation with a finite domain solver</H3>
    This library comes in two flavours: lib(fd_sets) which cooperates with
    lib(fd), and lib(ic_sets) which cooperates with lib(ic). This is relevant
    only for those constraints which involve integer variables, e.g. the
    cardinality argument in #/2, the weight argument in weight/3 and the
    booleans in membership_booleans/2. These will be represented as fd-
    or ic-variables respectively.

<H2>Examples</H2>
<PRE>
% Example program: Steiner triplets
% Compute NB triplets of numbers from 1 to N such that
% any two triplets have at most one element in common.
% Try steiner(9,Sets).

:- lib(fd_sets).
:- lib(fd).

steiner(N, Sets) :-
	NB is N * (N-1) // 6,		% compute number of triplets
	intsets(Sets, NB, 1, N),	% initialise the set variables
	( foreach(S,Sets) do
	    #(S,3)			% constrain their cardinality
	),
	( fromto(Sets,[S1|Ss],Ss,[]) do
	    ( foreach(S2,Ss), param(S1) do
		#(S1 /\ S2, C),		% constrain the cardinality
		C #=&lt; 1			% of pairwise intersections
	    )
	),
        label_sets(Sets).		% search

label_sets([]).
label_sets([S|Ss]) :-
        insetdomain(S,_,_,_),
	label_sets(Ss).
</PRE>
<H2>About</H2><UL COMPACT>
<LI><STRONG>Author: </STRONG>Joachim Schimpf, Neng-Fa Zhou
<LI><STRONG>Copyright &copy; </STRONG>Cisco Systems, Inc.
<LI><STRONG>Date: </STRONG>$Date: 2009/03/14 07:50:38 $
</UL>
<HR>Generated from fd_sets.eci on 2009-05-27 01:25
</BODY></HTML>
